package leetcode51_60;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @author shhjiang_001
 * @create 2020-06-19 23:23
 */

        /*
        给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
        按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
        "123"
        "132"
        "213"
        "231"
        "312"
        "321"
        */
public class Solution60 {
//    StringBuilder sb = new StringBuilder();
    String sb = "";
    int num = 0;
    public String getPermutation(int n, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        int pos = 0;
        method(list,k,n,pos);
        return sb;
    }

    private void method(ArrayList<Integer> list, int k, int n,int pos) {
        if (pos == n){
            num++;
            if (num==k){
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < list.size(); i++) {
                    builder.append(list.get(i));
                }
                sb = builder.toString();
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!list.contains(i)){
                list.add(i);
                method(list,k,n,pos+1);
                list.remove(list.size()-1);
            }
        }

    }
    @Test
    public void test(){
        String s = getPermutation(9, 62716);
        System.out.println(s);
    }
}
